|
An automatic sequence, called a ''k''-automatic sequence when one wants to indicate that the base of the numerals used is ''k'', is an infinite sequence of terms characterized by a finite automaton. The ''n''-th term of the sequence is a mapping of the final state of the automaton when its input is the digits of ''n'' in some fixed base ''k''.〔Allouche & Shallit (2003) p. 152〕〔Berstel et al (2009) p. 78〕 A ''k''-automatic set is a set of non-negative integers for which the sequence of values of its characteristic function is an automatic sequence: that is, membership of ''n'' in the set can be determined by a finite state automaton on the digits of ''n'' in base ''k''.〔Allouche & Shallit (2003) p. 168〕〔 An automaton reading the base ''k'' digits from the most significant is said to be ''direct reading'', and from the least significant is ''reverse reading''.〔Pytheas Fogg (2002) p. 13〕 However the two directions lead to the same class of sequences.〔Pytheas Fogg (2002) p. 15〕 Every automatic sequence is a morphic word.〔Lothaire (2005) p. 524〕 ==Automaton point of view== Let ''k'' be a positive integer, and ''D'' = (''E'', φ, ''e'') be a deterministic automaton where *''E'' is the finite set of states *φ : ''E''×() → ''E'' is the transition function * is the initial state also let ''A'' be a finite set, and π:''E'' → ''A'' a projection towards ''A''. Extend the transition function φ from acting on single digits to acting on strings of digits by defining the action of φ on a string ''s'' consisting of digits ''s''1''s''2...''s''''t'' as: : Define a function ''m'' from the set of positive integers to the set ''A'' as follows: : where ''s''(''n'') is ''n'' written in base ''k''. Then the sequence ''m'' = ''m''(1)''m''(2)''m''(3)... is called a ''k''-automatic sequence.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Automatic sequence」の詳細全文を読む スポンサード リンク
|